package bfs;

import javafx.util.Pair;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 给定一个 N 叉树，找到其最大深度。
 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
 * @author le
 */
public class MaxDepthOfTree
{
    public static void main(String[] args)
    {

    }

    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;
        } else {
            List<Integer> heights = new LinkedList<>();
            for (Node item : root.children) {
                heights.add(maxDepth(item));
            }
            return Collections.max(heights) + 1;
        }
    }

    public int max(Node root){
        Queue<Pair<Node, Integer>> stack = new LinkedList<>();
        if (root != null){
            stack.add(new Pair<>(root, 1));
        }

        int depth = 0;
        while(!stack.isEmpty()){
            Pair<Node, Integer> current = stack.poll();
            root = current.getKey();
            int cur = current.getValue();
            if (root != null){
                depth = Math.max(depth, cur);
                for(Node c : root.children){
                    stack.add(new Pair<>(c, cur+1));
                }
            }
        }
        return depth;
    }


    public int maxDepths(TreeNode node){
        Queue<TreeNode> queue = new LinkedList<>();
        if (node != null){
            queue.offer(node);
        }
        int depth = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                TreeNode tmp = queue.poll();
                if (tmp.left != null){
                    queue.offer(tmp.left);
                }
                if (tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
            depth += 1;
        }
        return depth;

    }
}
